package summer.graph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Solution1926 {
    public int nearestExit(char[][] maze, int[] entrance) {
        int[] dx = new int[]{-1, 1, 0, 0};
        int[] dy = new int[]{0, 0, 1, -1};
        int m = maze.length;
        int n = maze[0].length;
        boolean[][] used = new boolean[m][n];
        LinkedList<int[]> queue = new LinkedList<>();
        queue.add(entrance);
        used[entrance[0]][entrance[1]] = true;
        int dis = 0;
        while (!queue.isEmpty()) {
            dis++;
            int size = queue.size();
            while (size-- > 0) {
                int[] curs = queue.removeFirst();
                for (int i = 0; i < 4; i++) {
                    int x = curs[0] + dx[i];
                    int y = curs[1] + dy[i];
                    if (x < 0 || x >= m || y < 0 || y >= n) continue;
                    if (used[x][y]) continue;
                    if (maze[x][y] == '+') continue;
                    if (x == 0 || x == m - 1 || y == 0 || y == n - 1) return dis;
                    used[x][y] = true;
                    queue.add(new int[]{x, y});
                }
            }
        }
        return -1;
    }
}
